#include "ULCore_History.h"
#include "ULCore_BinFile.h"
#include "UL_Tools.h"
#include <fstream>
#include <algorithm>

#define EXAMPLE_BUFFER		"2012095 2012-08-14 17 24 27 28 29 30 02 24 29 17 27 28 30 324870412 476949363 3 9886677 92 239022 1161 3000 64836 200 1245851 10 1139552     5 5"
#define FORMAT_LINE_SIZE	(strlen(EXAMPLE_BUFFER) + 64)

ULC_History::ULC_History():totalSerials(0), serials(NULL), indexMap(NULL), repeatedFound(false), initFlag(false), hashFlag(false)
{
}

ULC_History::~ULC_History()
{
	if (initFlag == true){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": indexMap at " << indexMap << " serials at " <<  serials << endl;
#endif
		if (indexMap != NULL){
			delete[] indexMap;
		}

		if (serials != NULL){
			delete[] serials;
		}
		//hashSerials and repeatedRoots will be cleared automaticly
	}
}

#define BINARY_SEARCH_DELIMITER		15

int ULC_History::OptimizedBinarySearchSN(int leftIndex, int rightIndex, int serialNo)
{
	int midIndex;

	if (rightIndex < leftIndex){
		return -1;
	}

	if ((rightIndex - leftIndex + 1) <= BINARY_SEARCH_DELIMITER){
		//Use a loop to do searching
		for (int i = leftIndex; i <= rightIndex; i++){
			if (indexMap[i].sn == serialNo){
				return i;
			}
		}
		
		//Not found
		return -1;
	}

	midIndex = leftIndex + ((rightIndex - leftIndex) >> 1);

	if (indexMap[midIndex].sn == serialNo){
		return midIndex;
	}

	if (indexMap[midIndex].sn > serialNo){
		return OptimizedBinarySearchSN(leftIndex, midIndex - 1, serialNo);
	}else{
		return OptimizedBinarySearchSN(midIndex + 1, rightIndex, serialNo);
	}

}

int ULC_History::LookupIndex(int serialNo)
{
	//Binary search
	if (serialNo < indexMap[0].sn || serialNo > indexMap[totalSerials - 1].sn){
		return -1;
	}
	
	return OptimizedBinarySearchSN(0, totalSerials - 1, serialNo);
}

int ULC_History::LookupIndex(const char *date)
{
	for (int i = 0; i < totalSerials; i++){
		if (strcmp(date, indexMap[i].date) == 0){
			return i;
		}
	}

	return -1;
}

void ULC_History::SetupHashSerials()
{
	ULC_Serial *curSerial;

	if (serials == NULL){
		return ;
	}

	for (int i = 0; i < totalSerials; i++){
		curSerial = serials + i;
		hashSerials[curSerial->sortedBalls.blue].push_back(curSerial);
	}


	hashFlag = true;
}

void ULC_History::ClearHashSerials()
{
	for (int i = 1; i < 17; i++){
		hashSerials[i].clear();
	}

	hashFlag = false;
	repeatedFound = false;
}

void ULC_History::SetupIndexMap()
{
	ULC_Serial *serial;

	if (serials == NULL){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": serials has not been setup" << endl;
#endif
		return ;
	}

	if (indexMap != NULL){
		mapFlag = false;
		delete[] indexMap;
		indexMap = NULL;
	}
	
	indexMap = new struct ULC_HistoryIndexMap[totalSerials];

	if (indexMap == NULL){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": Cannot allocate enough memory for indexMap" << endl;
#endif
		return ;
	}

#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": Setting up indexMap..." << endl;
#endif
	for (int i = 0; i < totalSerials; i++){
		serial = serials + i;
		
		indexMap[i].sn = serial->sn;
		strcpy(indexMap[i].date, serial->date);		
		indexMap[i].index = i;
	}

	mapFlag = true;
}

void ULC_History::HashSetupRepeatedSerials(int hashList)
{
	ULC_Serial *curSerial_i, *curSerial_j;
	ULC_Serial *tmpSerial;
	list<ULC_Serial *>::iterator iter_i, iter_j;

	if (hashSerials[hashList].size() <= 1){
		return ;
	}

	for (iter_i = hashSerials[hashList].begin(); iter_i != hashSerials[hashList].end(); iter_i++){
		curSerial_i = *iter_i;
		//If curSerial_i has been marked as repeated already,skip this serial
		if (curSerial_i->repeatedRoot != NULL){
			continue;
		}	

		tmpSerial = curSerial_i;
		iter_j = iter_i;
		advance(iter_j, 1);
		
		while (iter_j != hashSerials[hashList].end()){
			//Compare red balls
			curSerial_j = *iter_j;

			if (curSerial_j->repeatedRoot != NULL){
				iter_j++;
				continue;
			}

			if (curSerial_i->sortedBalls == curSerial_j->sortedBalls){
				if (curSerial_i->repeatedRoot == NULL){
					//Mark as root node
					curSerial_i->repeatedRoot = curSerial_i;
					repeatedRoots.push_back(curSerial_i);
				}


				tmpSerial->nextRepeatedSerial = curSerial_j;
				curSerial_j->repeatedRoot = curSerial_i;

				tmpSerial = curSerial_j;
				repeatedFound = true;
			}

			iter_j++;
		}
	}

#ifdef ULC_HISTORY_DEBUG
	if (repeatedFound){
		cout << __func__ << ": Repeated serials found" << endl;
	}else{
		cout << __func__ << ": Repeated serials not found" << endl;
	}
#endif
}

void ULC_History::SetupRepeatedSerials()
{
	if (hashFlag == false || serials == NULL || totalSerials <= 1){
		return ;
	}
	
	repeatedFound = false;
	repeatedRoots.clear();

	for (int i = 1; i < 17; i++){
		//If repeated serials found, they must be in the same hash list because hashSerials are indexed by blue number
		HashSetupRepeatedSerials(i);
	}
}

int ULC_History::ParseBinHistory(const char *binFileName)
{
	if (binFileName == NULL){
		return -1;
	}

	totalSerials = ULC_BinFile::GetTotalSerials(binFileName);

#ifdef ULC_HISTORY_DEBUG
	cout << __func__ << ": totalSerials = " << totalSerials << endl;
#endif

	if (totalSerials <= 0){
		//File format incorrect or file is corrupted
		return -1;
	}
	
	//If already parsed
	if (initFlag == true && serials != NULL){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": serials already allocated" << endl; 
#endif
		delete[] serials;
		serials = NULL;
		initFlag = false;
		ClearHashSerials();
	}
	
	serials = new ULC_Serial[totalSerials];

	if (serials == NULL){
		return -1;
	}

	if (ULC_BinFile::LoadSerials(binFileName, serials) < 0){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": LoadSerials() failed" << endl; 
#endif
		delete[] serials;
		serials = NULL;
		return -1;
	}

	latestSerial = ULC_BinFile::GetLatestSerial(binFileName);
	
	if (latestSerial != serials[totalSerials - 1].sn){
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ": serials[" << totalSerials - 1 << "].sn(" <<  serials[totalSerials - 1].sn << ") does not equal file's latestSerial(" << latestSerial << ")" << endl; 
#endif
		delete[] serials;
		serials = NULL;
		return -1;
	}

	SetupHashSerials();
#ifdef ULC_HISTORY_DEBUG
	cout << __func__ << ": SetupHahsSerials() done" << endl;
#endif
	SetupRepeatedSerials();
#ifdef ULC_HISTORY_DEBUG
	cout << __func__ << ": SetupRepeatedSerials() done" << endl;
#endif
	SetupIndexMap();
#ifdef ULC_HISTORY_DEBUG
	cout << __func__ << ": SetupIndexMap() done" << endl;
#endif

	initFlag = true;

	return 0;
}

static void JumpToLine(ifstream &inf, int line)
{
	char fakeBuffer[FORMAT_LINE_SIZE];

	if (line == 1){
		inf.seekg(0, ios::beg);
		return ;
	}

	line--;

	while (line){
		inf.getline(fakeBuffer, FORMAT_LINE_SIZE);
		line--;
	}
}

int ULC_History::UpdateBinHistory(const char *txtFileName, const char *binFileName)
{
	int txtTotalSerials;
	int binTotalSerials;
	int diffSerials;
	ULC_Serial *updateSerials = NULL;
	char lineBuf[FORMAT_LINE_SIZE];
	ifstream inf;

	if (txtFileName == NULL || binFileName == NULL){
		return -1;
	}
	
	txtTotalSerials = UL_Tools::FileLinesCount(txtFileName);
	binTotalSerials = ULC_BinFile::GetTotalSerials(binFileName);

	if (txtTotalSerials <= 0 || binTotalSerials <= 0){
		return -1;
	}

	if (txtTotalSerials <= binTotalSerials){
		//Total serials are the same or txt file is older, no need to update binary file
#ifdef ULC_HISTORY_DEBUG
		cout << __func__ << ":No need to update binary file" << endl;
#endif
		return 0;
	}

	inf.open(txtFileName);

	if (inf.fail()){
		return -1;
	}
	
	diffSerials = txtTotalSerials - binTotalSerials;
	updateSerials = new ULC_Serial[diffSerials];
	
	if (updateSerials == NULL){
		inf.close();
		return -1;
	}

	JumpToLine(inf, txtTotalSerials - diffSerials + 1);

	int index = 0;

	while (!inf.eof()){
		memset(lineBuf, 0, FORMAT_LINE_SIZE);
		inf.getline(lineBuf, FORMAT_LINE_SIZE);
		
		if (index == diffSerials){
			break;
		}

		updateSerials[index].ParseLineBuffer(lineBuf);
		index++;
	}

	ULC_BinFile::AppendSerials(binFileName, diffSerials, updateSerials);
	
	delete[] updateSerials;
	inf.close();
	return 0;
}

int ULC_History::GenerateBinHistory(const char *txtFileName, const char *binFileName)
{
	ifstream inf;
	int txtTotalSerials;
	ULC_Serial *allSerials;
	char lineBuf[FORMAT_LINE_SIZE];
	
	if (txtFileName == NULL || binFileName == NULL){
		return -1;
	}
	
	txtTotalSerials = UL_Tools::FileLinesCount(txtFileName);
#ifdef ULC_HISTORY_DEBUG
	cout << __func__ << ": txtTotalSerials = " << txtTotalSerials << endl;
#endif
	if (txtTotalSerials <= 0){
		return -1;
	}	
	
	allSerials = new ULC_Serial[txtTotalSerials];

	if (allSerials == NULL){
		return -1;
	}

	inf.open(txtFileName);

	if (inf.fail()){
		delete[] allSerials;
		return -1;
	}

	int index = 0;

	while (!inf.eof()){
		memset(lineBuf, 0, FORMAT_LINE_SIZE);
		inf.getline(lineBuf, FORMAT_LINE_SIZE);

		if (index == txtTotalSerials){
			break;
		}
		
		//Temp debug
		//cout << "[----" <<lineBuf << "----]"<< endl;
		
		allSerials[index].ParseLineBuffer(lineBuf);
		index++;
	}
	
	inf.close();

	//Create a binary file
	ULC_BinFile::SaveSerials(binFileName, txtTotalSerials, allSerials);

	delete[] allSerials;
	return 0;
}

ULC_Serial *ULC_History::LookupSerial(int serialNo)
{
	int index;

	if (initFlag == false || serials == NULL ||  mapFlag == false || serialNo <= 0){
		return NULL;
	}

	index = LookupIndex(serialNo);	

	if (index == -1){
		return NULL;
	}

	return serials + index;
}

ULC_Serial *ULC_History::LookupSerial(const char *date)
{
	int index;

	if (initFlag == false || serials == NULL || mapFlag == false || date == NULL){
		return NULL;
	}

	index = LookupIndex(date);	

	if (index == -1){
		return NULL;
	}

	return serials + index;
}

ULC_Serial *ULC_History::LookupRange(int startSerialNo, int &count)
{
	int index;

	if (initFlag == false || mapFlag == false || startSerialNo <= 0 || count <= 0){
		count = 0;
		return NULL;
	}

	index = LookupIndex(startSerialNo);

	if (index == -1){
		count = 0;
		return NULL;
	}

	if ((index + count) > totalSerials){
		count = totalSerials - index;
	}

	return serials + index;
}

ULC_Serial *ULC_History::LookupRange(const char *startDate, int &count)
{
	int index;

	if (initFlag == false || mapFlag == false || startDate == NULL || count <= 0){
		count = 0;
		return NULL;
	}

	index = LookupIndex(startDate);

	if (index == -1){
		count = 0;
		return NULL;
	}

	if ((index + count) > totalSerials){
		count = totalSerials - index;
	}

	return serials + index;

}

int ULC_History::LookupSerial(list<ULC_Serial *> &resultList, ULC_Balls &balls)
{
	list<ULC_Serial *> *lookupList = NULL;
	list<ULC_Serial *>::iterator iter;
	ULC_Serial *serial = NULL;

	if (balls.blue < UL_BALL_MIN_BLUE  || balls.blue > UL_BALL_MAX_BLUE){
		return -1; 
	}

	lookupList = &hashSerials[balls.blue];

	if (lookupList->empty()){
		return -1;
	}
	
	for (iter = lookupList->begin(); iter != lookupList->end(); iter++){
		serial = *iter;

		if (serial->sortedBalls == balls){
			break;
		}
	}

	if (iter == lookupList->end()){
		//Not found
		return -1;
	}
	
	resultList.clear();

	while (serial){
		resultList.push_back(serial);
		serial = serial->nextRepeatedSerial;
	}

	return 0;
}

int ULC_History::LookupSerialsByBlueBall(list<ULC_Serial *> &resultList, int blueNumber)
{
	if (blueNumber < UL_BALL_MIN_BLUE || blueNumber > UL_BALL_MAX_BLUE){
		return -1;
	}

	if (hashSerials[blueNumber].empty()){
		return -1;
	}

	resultList = hashSerials[blueNumber];

	return 0;
}

bool ULC_History::RepeatedSerialsFound()
{
	return repeatedFound;
}

void ULC_History::ShowRepeatedSerials()
{
	ULC_Serial *curSerial;
	list<ULC_Serial *>::iterator iter;

	if (initFlag == false || repeatedFound == false){
		return ;
	}

	cout << "Repeated Serials(" << repeatedRoots.size() << " root nodes):" << endl;
	for (iter = repeatedRoots.begin(); iter != repeatedRoots.end(); iter++){
		curSerial = *iter;

		cout << "+++++++++++++++++++++++++++++++++++++" << endl;
		cout << "Repeated Serial Root: " << curSerial->sn <<  endl;
		while (curSerial != NULL){
			cout << *curSerial << endl;
			curSerial = curSerial->nextRepeatedSerial;	
		}
		cout << "+++++++++++++++++++++++++++++++++++++" << endl;
	}
}

ULC_Serial *ULC_History::GetLatestSerial()
{
	if (initFlag == false || serials == NULL){
		return NULL;
	}

	return serials + (totalSerials - 1);
}

ULC_Serial *ULC_History::GetLatestSerials(int &nSerials)
{
	if (initFlag == false || serials == NULL){
		return NULL;
	}

	if (nSerials > totalSerials){
		nSerials = totalSerials;
	}

	return serials + (totalSerials - nSerials);
}

int ULC_History::GetLatestNSerialsBlues(list<int> &result, int &nSerials)
{
	ULC_Serial *beginSerial;
	list<int>::iterator iter;
	int i;

	if (initFlag == false || serials == NULL){
		return -1;
	}

	result.clear();

	if (nSerials > totalSerials){
		//All blues are contained
		nSerials = totalSerials;
		
		for (i = 1; i < UL_BALL_MAX_BLUE; i++){
			result.push_back(i);
		}

		return 0;
	}

	beginSerial = serials + (totalSerials - nSerials);

	for (i = 0; i < nSerials; i++){
		iter = find(result.begin(), result.end(), beginSerial[i].sortedBalls.blue);
		if (iter == result.end()){
			result.push_back(beginSerial[i].sortedBalls.blue);
		}

		if (result.size() == UL_BALL_MAX_BLUE){
			break;
		}
	}	

	result.sort();

	return 0;
}

int ULC_History::GetLatestNSerialsWithBlueNumber(list<ULC_Serial *> &result, int &nSerials, int blueNumber)
{
	list<ULC_Serial *>::iterator iter;
	int count;

	if (initFlag == false || hashFlag == false || blueNumber < UL_BALL_MIN_BLUE || blueNumber > UL_BALL_MAX_BLUE){
		return -1;
	}

	result.clear();

	if (nSerials > hashSerials[blueNumber].size()){
		nSerials = hashSerials[blueNumber].size();
		result = hashSerials[blueNumber]; 
		return 0;
	}
	
	iter = hashSerials[blueNumber].end();
	iter--;
	count = nSerials;

	while (count > 0){
		result.push_front(*iter);
		iter--;
		count--;
	}

	return 0;
}

int ULC_History::GetTotalSerials()
{
	return totalSerials;
}

int ULC_History::CaculateGap(ULC_Serial *serial1, ULC_Serial *serial2)
{
	int index1, index2;

	if (initFlag == false || serial1 == NULL || serial2 == NULL){
		return -1;
	}
	
	//Use serial number as argument(Binary search is much more faster)
	index1 = LookupIndex(serial1->sn);
	index2 = LookupIndex(serial2->sn);

	if (index1 == -1 || index2 == -1){
		return -1;
	}

	if (index1 == index2){
		return 0;
	}

	if (index1 > index2){
		return index1 - index2 - 1;
	}

	return index2 - index1 - 1;
}

int ULC_History::CaculateGap(int serialNo1, int serialNo2)
{
	int index1, index2;

	if (initFlag == false){
		return -1;
	}

	index1 = LookupIndex(serialNo1);
	index2 = LookupIndex(serialNo2);

	if (index1 == -1 || index2 == -1){
		return -1;
	}

	if (index1 > index2){
		return index1 - index2 - 1;
	}

	return index2 - index1 - 1;
}
